﻿using System;
using System.Collections.Generic;
using System.Text;

namespace DataSort
{
    public static class Sort
    {
         #region 冒泡排序
            /// <summary>
            /// 冒泡排序，结果升序排列
            /// <para>调用：arry.BubbleSort();</para>
            /// </summary>
            /// <param name="arry">要排序的整数数组</param>
            public static void BubbleSort(this int[] arry)
            {
                for (int i = 0; i < arry.Length; i++)
                {
                    for (int j = 0; j < arry.Length - 1 - i; j++)
                    {
                        //比较相邻的两个元素，如果前面的比后面的大，则交换位置
                        if (arry[j] > arry[j + 1])
                        {
                            int temp = arry[j + 1];
                            arry[j + 1] = arry[j];
                            arry[j] = temp;
                        }
                    }
                }
            }
            #endregion

            #region 快速排序
            /// <summary>
            /// 快速排序
            /// <para>调用：arry.QuickSort(0, arry.Length-1 );</para>
            /// </summary>
            /// <param name="arry">要排序的数组</param>
            /// <param name="left">低位</param>
            /// <param name="right">高位</param>
            public static void QuickSort(this int[] arry, int left, int right)
            {
                //左边索引小于右边，则还未排序完成
                if (left < right)
                {
                    //取中间的元素作为比较基准，小于他的往左边移，大于他的往右边移
                    int middle = arry[(left + right) / 2];
                    int i = left - 1;
                    int j = right + 1;
                    while (true)
                    {
                        //移动下标，左边的往右移动，右边的向左移动
                        while (arry[++i] < middle && i < right) ;
                        while (arry[--j] > middle && j > 0) ;
                        if (i >= j)
                            break;
                        //交换位置
                        int number = arry[i];
                        arry[i] = arry[j];
                        arry[j] = number;

                    }
                    QuickSort(arry, left, i - 1);
                    QuickSort(arry, j + 1, right);
                }
            }
            #endregion

            #region 直接插入排序
            /// <summary>
            /// 直接插入排序
            /// <para>调用：arry.InsertSort();</para>
            /// </summary>
            /// <param name="arry">要排序的数组</param>
            public static void InsertSort(this int[] arry)
            {
                //直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的
                for (int i = 1; i < arry.Length; i++)
                {
                    //如果当前元素小于其前面的元素
                    if (arry[i] < arry[i - 1])
                    {
                        //用一个变量来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位
                        int temp = arry[i];
                        int j = 0;
                        for (j = i - 1; j >= 0 && temp < arry[j]; j--)
                        {
                            arry[j + 1] = arry[j];
                        }
                        arry[j + 1] = temp;
                    }
                }
            }
            #endregion

            #region 希尔排序
            /// <summary>
            /// 希尔排序
            /// <para>调用：arry.ShellSort();</para>
            /// </summary>
            /// <param name="arry">待排序的数组</param>
            public static void ShellSort(this int[] arry)
            {
                int length = arry.Length;
                for (int h = length / 2; h > 0; h = h / 2)
                {
                    //here is insert sort
                    for (int i = h; i < length; i++)
                    {
                        int temp = arry[i];
                        if (temp < arry[i - h])
                        {
                            for (int j = 0; j < i; j += h)
                            {
                                if (temp < arry[j])
                                {
                                    temp = arry[j];
                                    arry[j] = arry[i];
                                    arry[i] = temp;
                                }
                            }
                        }
                    }
                }
            }
            #endregion

            #region 简单选择排序
          
            /// <summary>
            /// 简单选择排序
            /// <para>调用：arry.SimpleSelectSort();</para>
            /// </summary>
            /// <param name="arry">待排序的数组</param>
            public static void SimpleSelectSort(this int[] arry)
            {
                int tmp = 0;
                int t = 0;//最小数标记
                for (int i = 0; i < arry.Length; i++)
                {
                    t = i;
                    for (int j = i + 1; j < arry.Length; j++)
                    {
                        if (arry[t] > arry[j])
                        {
                            t = j;
                        }
                    }
                    tmp = arry[i];
                    arry[i] = arry[t];
                    arry[t] = tmp;
                }
            }
            #endregion

            #region 堆排序
          
            /// <summary>
            /// 堆排序
            /// <para>调用：arry.HeapSort(arry.Length);</para>
            /// </summary>
            /// <param name="arry">待排序的数组</param>
            /// <param name="top"></param>
            public static void HeapSort(this int[] arry, int top)
            {
                //List<int> topNode = new List<int>();

                for (int i = arry.Length / 2 - 1; i >= 0; i--)
                {
                    HeapAdjust(arry, i, arry.Length);
                }

                for (int i = arry.Length - 1; i >= arry.Length - top; i--)
                {
                    int temp = arry[0];
                    arry[0] = arry[i];
                    arry[i] = temp;
                    HeapAdjust(arry, 0, i);
                }
            }

            /// <summary>
            /// 构建堆
            /// </summary>
            /// <param name="arry"></param>
            /// <param name="parent"></param>
            /// <param name="length"></param>
            private static void HeapAdjust(int[] arry, int parent, int length)
            {
                int temp = arry[parent];

                int child = 2 * parent + 1;

                while (child < length)
                {
                    if (child + 1 < length && arry[child] < arry[child + 1]) child++;

                    if (temp >= arry[child])
                        break;

                    arry[parent] = arry[child];

                    parent = child;

                    child = 2 * parent + 1;
                }

                arry[parent] = temp;
            }

            #endregion

            #region 归并排序
          
            /// <summary>
            /// 归并排序
            /// <para>调用：arry.MergeSort(0, arry.Length);</para>
            /// </summary>
            /// <param name="arry">待排序数组</param>
            /// <param name="first"></param>
            /// <param name="last"></param>
            public static void MergeSort(this int[] arry, int first, int last)
            {
                if (first + 1 < last)
                {
                    int mid = (first + last) / 2;

                    MergeSort(arry, first, mid);
                    MergeSort(arry, mid, last);

                    Merger(arry, first, mid, last);
                }
            }
            /// <summary>
            /// 归并
            /// </summary>
            /// <param name="arry"></param>
            /// <param name="first"></param>
            /// <param name="mid"></param>
            /// <param name="last"></param>
            private static void Merger(int[] arry, int first, int mid, int last)
            {
                Queue<int> tempV = new Queue<int>();
                //设置indexA，并扫描subArray1 [first,mid]
                //设置indexB,并扫描subArray2 [mid,last]
                int indexA = first;
                int indexB = mid;
                //在没有比较完两个子标的情况下，比较 v[indexA]和v[indexB]
                //将其中小的放到临时变量tempV中
                while (indexA < mid && indexB < last)
                {
                    if (arry[indexA] < arry[indexB])
                    {
                        tempV.Enqueue(arry[indexA]);
                        indexA++;
                    }
                    else
                    {
                        tempV.Enqueue(arry[indexB]);
                        indexB++;
                    }
                }
                //复制没有比较完子表中的元素
                while (indexA < mid)
                {
                    tempV.Enqueue(arry[indexA]);
                    indexA++;
                }
                while (indexB < last)
                {
                    tempV.Enqueue(arry[indexB]);
                    indexB++;
                }
                int index = 0;
                while (tempV.Count > 0)
                {
                    arry[first + index] = tempV.Dequeue();
                    index++;
                }
            }

            #endregion

            #region 基数排序
            /// <summary>
            /// 基数排序
            /// <para>约定：待排数字中没有0,如果某桶内数字为0则表示该桶未被使用,输出时跳过即可</para>
            /// <para>调用：arry.RadixSort();</para>
            /// </summary>
            /// <param name="arry">待排数组</param>
            /// <param name="array_x">桶数组第一维长度</param>
            /// <param name="array_y">桶数组第二维长度</param>
            public static void RadixSort(this int[] arry, int array_x = 10, int array_y = 100)
            {
                /* 最大数字不超过999999999...(array_x个9) */
                for (int i = 0; i < array_x; i++)
                {
                    int[,] bucket = new int[array_x, array_y];
                    foreach (var item in arry)
                    {
                        int temp = (item / (int)Math.Pow(10, i)) % 10;
                        for (int l = 0; l < array_y; l++)
                        {
                            if (bucket[temp, l] == 0)
                            {
                                bucket[temp, l] = item;
                                break;
                            }
                        }
                    }
                    for (int o = 0, x = 0; x < array_x; x++)
                    {
                        for (int y = 0; y < array_y; y++)
                        {
                            if (bucket[x, y] == 0) continue;
                            arry[o++] = bucket[x, y];
                        }
                    }
                }
            }
            #endregion
        }
    }
